PHASE4: Initialize and Run Contraction by PostGreSQL
Summary
Run hierarchical contraction over entire graph to identify and create shortcuts -- meaning the cost-effective paths between nearby nodes at various distance.
WARNING This is the largest phase of the project -- covering ~70% of total processing time of the entire project. It could run for more than four months
Below picture illustrates contraction hierarchy. Essentially, if a shortest path is found between two nodes, Nf and Nt, a contracted edge is created between them. If all such paths originating from Nf has been considered, then node Nf is marked are contracted -- effectively implying that only the contracted edges of Nf are the shortest paths and nothing else.
Ref: C:\GangaToKaveri\docs\graph_contraction_illustration.jpg
Run-time estimate:
At ~14msec per node, a batch of 1440000 nodes will take 336min or ~225 days for PROD
Reduction of each msec will reduce batch execution time by 24min
STEP1: Initialize Contraction Ordering (bidirectional map)
Connect to PostGreSql container
Truncate tables:
SET statement_timeout = 19200000; SET lock_timeout=1200000; SET work_mem TO '2048MB';
TRUNCATE TABLE public.contraction_init;
TRUNCATE TABLE public.node_out_shortcuts;
TRUNCATE TABLE public.node_in_shortcuts;
NOTE:
Truncate is done to reset any past intermediate/incomplete/partial runs
Configure contraction related settings
Config Parameters:
Unlike with pagedmap, totalFileBackedContractorMapsToCache can be set to quite large number (since memory is not used up!)
maxNeighborCost is the upper limit of any edge cost (60times5.0elevationUnit30costPerElevation) -- so that any ridge-like noisy neighborhood elevation values causes path-calculation issue (e-g., cost of 151930 for edge between 51838320 and 51859919)
WARNING If Soil-Cost has already been applied to node-edges, then for maxNeighborCost, use 360times5.0elevationUnit30costPerElevation=27000
maxNeighborCost is multiplied by 3 since the cost multipliers for most of soil types are <= 3 (very few has 3.5 and 4)
pagedContractorExecutorThreads is set to 16 (8 for DEV) -- since initialize does lots of findShortcut; but doesn't save the contractions (read-only shortcuts!)
pagedContractorParallelBatchSize is 1 since batch is already large for pagedGraphGridNodesInRowpagedGraphGridNodesInColumn (3240000)
Shortcut caches are set to -1 -- since Initialize phase of contraction does one-time calculation of findShortcut per node
However, dbContractorShortcutBatchSize is set to 1000 -- as Shortcut caches will run on write-only mode (for future usage)
pagedContractorBackupIncrWaitSec is reduced to 900 (from default 1800) since initialize stage makes little updates
tempMonitoringEnabled is enabled for old PROD on server that CPU-heats up on high-load
pausedNodeAccessSettings is enabled for old PROD on server -- so that pausedNodeAccessSvc will use low PauseEveryNCalls during nights than days
nodeAccessPauseEveryNCalls is reduced to 250 (from default 1000) since initialize stage make short but frequent searches
nohup ${PCH_APP_HOME}/run_GraphContractor_Batches_by_db.sh --action initializeContractor --paginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json --newPaginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json > $PCH_LOG_HOME/nohup.out 2>&1 &
WARNING for very first batch-call, include "--yesIReallyWantToDo true"
<<Will run (TOTAL_NODES_PER_BATCH / TOTAL_NODES) number of batches>>
tail -f $PCH_LOG_HOME/GangaToKaveri.log
NOTE:
For DBMap and DB ContractionOrdering: Each batch typically takes 10.5 minutes for batch of 1440000 nodes for ~6days
STEP2: Review initialization of bidirectional map in DB storage
SET statement_timeout = 3600000;
SELECT COUNT(*) AS total_contracted_nodes FROM contraction_init;
total_contracted_nodes
------------------------
1350902211
WARNING
total_contracted_nodes MUST be close to totalNodes in runtime_cost_spec_by_db.json (based on number of sea-area in project scope)
SELECT edge_count_reduction, COUNT(*) AS total_edge_count_reduction FROM contraction_init GROUP BY edge_count_reduction ORDER BY edge_count_reduction DESC;
edge_count_reduction | total_edge_count_reduction
----------------------+----------------------------
16 | 127412413
15 | 3349234
14 | 10316528
13 | 6354369
12 | 13334225
11 | 13826331
10 | 16654957
9 | 17543437
8 | 25753293
7 | 35745537
6 | 49274117
5 | 68479831
4 | 102356987
3 | 151698159
2 | 224176433
1 | 294108816
0 | 190517544
edge_count_reduction | total_edge_count_reduction
----------------------+----------------------------
16 | 127412413
15 | 3349234
14 | 10316528
13 | 6354369
12 | 13334225
11 | 13826331
10 | 16654957
9 | 17543437
8 | 25753293
7 | 35745537
6 | 49274117
5 | 68479831
4 | 102356987
3 | 151698159
2 | 224176433
1 | 294108816
0 | 190517544
STEP3: Backup the stage completion
Take a full DB backup as baseline -- since "Contract all in batches" is going to run for ~100 days
/bin/cp ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json ${G2K_DATA_HOME}/runtime_cost_spec_by_db_post_initialize_contractor_date +%Y%m%d.json
STEP4a: Initialize contraction-state or reset any previous partial batch-runs
WARNING This is a REQUIRED step for first run or for resetting any previous partial batch-runs that should be erased
${PCH_APP_HOME}/run_GraphContractor.sh --action resetContractionState --yesIReallyWantToDo true --paginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json
NOTE:
resetContractionState creates new row entry in config_log table by collecting totalNodeGrids, totalNodes, parallelBatchSize from runtime_cost_spec_by_db.json
STEP4b: Stage1 First, and Middle stage contraction: (for 85% of batches)
Config Parameters:
pagedContractorExecutorThreads is set to 1 since contraction is internally using parallel streams.
graphGridDeserializerPendingTasksSize is reduced to 50 (DEV: 35) (graphGridTasksForceWaitIdleCheckLimit to 40/25) to keep only few pending tasks in UPSERTs pipeline (waiting for completion -- if needed)
graphGridDeserializingThreads is increased to 5 (DEV: 3) and graphDBDirtyNodesBatchSize, and graphDBDirtyEdgesBatchSize are reduced to 200/500 (or more defensive: 150/300) -- so that changes are written to DB often -- to avoid "prehydrateNodeEdges: mismatched edge size for node"
pagedContractorPreComputeShortcutsEnabled is set to true if we run a sepeate pre-compute node/server (see below)
pagedContractorParallelBatchSize is 1 since batch is already large for pagedGraphGridNodesInRow*pagedGraphGridNodesInColumn (1440000/3240000)
pagedContractorNodeShortcutsCacheSize is set to 1500000 on > 56GB Heap; or to 500000, and other ShortcutsCacheSize(s) are used
dbContractorShortcutBatchSize is set to 1000 (500 in DEV) -- so that batch insert happens to database writes
dbContractorInitBatchSize is increased from 2000 to 10000 on PROD since there are millions of add contractions in every batch
graphDBFetchNodeBatchSize is set to 500 -- as higher value causes longer query execution time when nodes have more edges (as contraction progresses)
contractionNodesToReorderBatchSize is set to 200 (100 in DEV) -- too low value reduces concurrency but too high value will cause slowness due to large neighbor node queries
Cache allocation:
Initialliy (for first 5 batches with millions of ADD_CONTRACTION_EDGES), keep 5M node cache; 2M edge cache; 5K new edge cache; 10K shortcut cache -- as contraction needs more nodes than individual edges
For mid-order batches (6-65 with 100s of thousands of ADD_CONTRACTION_EDGES), you may keep node cache same (or less); 5M edge; 50K shortcut cache
With 28GB JRE, and graphPrehydrateNodeEdges, keep secondaryCacheNodeSize below 6291456 -- as 6MB node (and edges) leads to memory thrashing.
secondaryCacheEdgeSize is set to small to serve only for first/second edges.
Tune dbContractorCacheSize in such a way that fillPrefetchedMap activity runs in ~5minute cycle
Set onCurrentNodeIdSetBusyCycleWaitMSec to 50000 on server or 150000 on Laptop
pagedContractorProfitableThreshold is almost disabled by very low value
pagedContractorProfitableThreshold may be set to 0 -- based on logThresholdMetric observation that 6500 nodes out of 810000 became unprofitable ( < 0) -- with max going up to 46
~130,000 nodes/810000 becomes unprofitable if threshold is > 0
accessPerformanceParameters is for three stages of contraction process. Initially it runs slow due to lack of contexts/caches. In the end it runs slow due to revisiting of already-contracted nodes.
contractionPreComputeShortcutsExecutorThreads is set to 40 on PROD; 6 on DEV
dbContractorInitRemoveBatchSize is set to small (250) to avoid too many deadlocks with INSERTS. (Reducing it too low will slow the constraction performance)
solutionToEdgeRatioBoundaries is edge counts of nodes that let to pick solutionToEdgeRatioProfitableLimits. Hence last value should be very large
pagedContractorBackupByBatchNoOffset is set to take more incremental backups (~ one per day) in prod and full backup every ~5 days -- as full backup takes over four hours
pagedContractorBackupFullEveryHrs is set to trigger full backup -- in case a batch has been run for more than 28hrs (e-g., initial batches)
onLookAheadNodeIdSetConcurrentThreads is set based on number of CPU cores on database server
shutdownInMiddleForNodeProcessTimeAveMSec, and shutdownInMiddleForTotalProcessTimeMinutes are set to trigger stop-in-middle for slow running process (lest it gets into repeated JVM garbage collection)
Unlike with pagedmap, totalFileBackedContractorMapsToCache can be set to quite large number (since memory is not used up!)
For very first batch (that needs state context resets):
nohup ${PCH_APP_HOME}/run_GraphContractor_Batches_by_db.sh --action contractByBatch --yesIReallyWantToDo true --paginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json --newPaginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json > $PCH_LOG_HOME/nohup.out 2>&1 &
WARNING
First batch will reset certain state contexts (such as contractionProgress) that are crucial to contraction ordering.
This should not be done after first batch
Hence you should pass yesIReallyWantToDo to confirm
NOTE:
First batch could run for very long (~4hrs)
For all subsequent batches:
nohup ${PCH_APP_HOME}/run_GraphContractor_Batches_by_db.sh --action contractByBatch --paginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json --newPaginationspec ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json > $PCH_LOG_HOME/nohup.out 2>&1 &
tail -f $PCH_LOG_HOME/GangaToKaveri.log
NOTE:
Runs in 50/4/35msec per node (initial/middle/last stages) for 85 days in ~1250 batches
During middle stage, the process could have slow performance of initial/last stage, see below
To monitor performance: tail -f ${PCH_LOG_HOME}/GangaToKaveri.log | grep "batch-status: nodesProcessed"
example log: batch-status: nodesProcessed delta/average: 5.78/8.03 msec/node 607386/1440000/603359, timeSoFar delta/total: 08s.320/01h:21m:18s.435 msec
admin/grafa_adm_pwd
Slow performance during middle stage:
Two or three times during middle stage, the process will be slow with following symptoms:
Ref: C:\GangaToKaveri\docs\g2k_low_cache_hit_high_node_fetch_contraction.png
Cause:
The Initialized Contraction-Init has been fully visited once and process is starting to revisit them. Hence, most of shortcuts have to be recomputed -- leading to large node/edge fetch
Since it is revisiting, not too many contraction edges get added
Resolution:
To improve the performance, temporarily set following (particularly isLowCacheHitsMode) in "normalStage" section:
"isLowCacheHitsMode": true,
"pagedContractorCommitStages": 6, <-- Increased
"secondaryCacheNodeSize": 8388608, <-- Decreased
"shutdownInMiddleForNodeProcessTimeAveMSec": 180, <-- Increased
"batchedNodeAccessMaxWaitMSec": 2, <-- Increased
STEP4c: Stage2 Last stage contraction: (for last 15% of batches)
Ref: C:\GangaToKaveri\docs\g2k_beginning_of_last_stage_of_contraction.png
- Very Low contraction edges added
- High node/edge fetched from DB
- Very Low node/edge, and shortcut cache hits
- High shortcut reads
- High Djkstra run-time
It starts around batch#1185 and runs till batch#1210
NOTE:
Doing the last-stage tuning is OPTIONAL. It reduces the cache usage in such a way that the contraction process won't get restarted in the middle due to memory issue. You may CHOOSE to leave the process in middle-stage itself with higher cache usage -- as contraction process has built-in restart-in-the-middle capability.
vi ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json
"dbContractorInitBatchSize": 2000,
"dbContractorInitBatchSize": 2000,STEP4d: End batch(es) of contraction
At the end:After revisiting all Contraction-Inits, the process will exhaust it completely and end. The batch will self-terminate
The batches of contraction process would end by itself when all node entries in contraction_init table has been exhausted.
However -- after over 90% nodes have been exhausted, the contraction process would become increasingly less productive:
Time taken per each batch would become longer during last stages
Hence number of nodes exhausted in contraction_init table will become lesser and lesser
Alternatively, you can end the contraction batches if performance begins to show high degradation:
Ref: C:\GangaToKaveri\docs\g2k_stage_before_last_stage_of_contraction.png
NOTE:
When process began at first batch, all nodes would have started with 0 edge-reduction
There are few nodes (<10 per reductions) that got edge-reduction by large numbers
There are some nodes (<100000 per reductions) that didn't get much of edge-reduction
~10 million of nodes with the more than 10 edge-reductions become less productive
After this degradation, it gets further slowness:
Ref: C:\GangaToKaveri\docs\g2k_ending_of_last_stage_of_contraction.png
- Batch runs for 3-5 times longer-time than before
- Very Low addition of new contraction edge
- 2-3 times more node/edges are fetched
- 3-4 time lower node/edge cache hits and shortcut cache hits
End the process in the middle
With less productive processing AND after over 90% nodes processed, you may choose the end the contraction process manually:
/bin/mv ${PCH_DATA_HOME}/stop_contraction_batches_in_middle_flag.yes ${PCH_DATA_HOME}/stop_contraction_batches_in_middle_flag.no
This will mark the current contraction batch to complete but will not procede to start the next batch.
STEP5: Post-contraction activities
Backup the contraction process settings:
/bin/cp ${G2K_DATA_HOME}/runtime_cost_spec_by_db.json ${G2K_DATA_HOME}/runtime_cost_spec_by_db_contraction_completed_`date +%Y%m%d`.json
Cleanup unused tables:
Connect to PostGreSql container
Truncate tables:
TRUNCATE TABLE public.contraction_init;
TRUNCATE TABLE public.contraction_init_prefetch;
TRUNCATE TABLE public.node_out_shortcuts;
TRUNCATE TABLE public.node_in_shortcuts;
TRUNCATE TABLE public.node_out_shortcuts_cache;
TRUNCATE TABLE public.node_in_shortcuts_cache;
NOTE:
Truncate is done to release disk space for other usages -- as contraction related tables are no more needed
~~~~~ Take FULL DB backup ~~~~~
Contraction Performance Reference
Performance of Initial Stage
Contraction average speed of ~25msec per node
Large number of shortcuts generated (dirty)
Low contractions added (nodes are getting less dirty)
Low shortcut cache-hits (no prior knowledge in storage) ~100
Example log: batch-status: nodesProcessed delta/average: 59.39/50.35 msec/node 495617/1440000/494410, timeSoFar delta/total: 01m:25s.517/06h:55m:55s.325 msec
Ref: C:\GangaToKaveri\docs\g2k_first_batches_of_contraction.png
End of Initial Stage:
Ref: g2k_end_of_first_stage_of_contraction.png
Auto-recovering slow contraction reaching low-memory:
Ref: g2k_slow_batch_contraction_auto_restarted.png
Performance of Normal Stage
Contraction average speed of ~7msec per node
High shortcut cache-hits (good prior knowledge in storage) ~1.5K
Example log: batch-status: nodesProcessed delta/average: 4.25/3.91 msec/node 709097/1440000/428058, timeSoFar delta/total: 06s.124/46m:14s.973 msec
General Performance during Normal Stage
Ref: g2k_during_normal_stage_of_contraction.png
Intermittent Slowness during Normal Stage
It is expected for performance to degrade by 50% once a while -- due to redoing contractions:
Process-time doubled/tripled
Cache-hits halved
Node fetches doubled
Compared to Initial and Last stages, these degradations are not drastic. Hence, no action is needed to be taken
Ref: g2k_slowness_during_normal_stage_of_contraction.png
Performance of Last Stage
Contraction average speed of ~20msec per node
Ref: C:\GangaToKaveri\docs\g2k_contraction_last_stage_performance.png